2023 알고리즘 중간고사

(1) 시험시간 : 4월 17일(월요일) 오전 8시 30분 - 10시 15분

(2) 풀이의 중간과정을 잘 기술해서 채점자에게 도움이 되도록 하세요.

(3) 뒷면에 답을 쓰게 되면 이 사실을 표시하시기 바랍니다.

(4) 채점자가 의도를 알 수 있도록 꼼꼼하고 친절하게 기술하세요.

학번	이름	감독자 확인

문제 (배점)	점수	문제 (배점)	점수
1 (30)		4 (20)
2 (20)		5 (40)
3 (30)		6 (30)
		총합계 (170)

[1] 다음 제시된 코드에서 함수 foo( )의 수행을 basic operation으로 했을 때의 time complexity [eqn: f(N)]을 계산하시오. 만일 closed form이 가능하면 closed form으로, 그것이 불가능하면 [eqn: THETA ( ~)], 이것도 불가능하면 [eqn: O(~)]로 표시하시오. 단 과정을 충분히 설명해야 함.

int i, w, d[N] ; i = N while( i > 1 ) { foo(i) ; i = i / 2 ; // 정수 나눗셈 for(w=0 ; w <= i ; w++) foo(w) ; }	[eqn: f(N)]
# Python Code N= len( Dlist ) c = 0 for i in range(1,N+1): m = N//i # 정수 나눗셈 for j in range(m) : foo(i+j)	[eqn: f(N)]
//foo( )가 두 군데임 read N ; while( N > 1 ) { foo( N ); N = N / 2 ; for(i=1 ; i <= N ; i++) { foo( i ) ; } } // end of while	[eqn: f(N)]

[2] 다음 recursion으로 정의된 함수의 asymptotic order를 계산하여 제시하시오.

a) [eqn: Q(1)=1,~Q(N`)=Q(N-3)+ sqrt {N}]

b) [eqn: T(1)=1,~T`(N`)=T`(N/3)+N ^{`2}]

[3] 두 사람 {F, S}가 바둑돌로 게임을 한다. N개의 돌이 담긴 통에서 두 사람이 차례대로 돌아가면서 정해진 규칙에 따라서 돌을 꺼내 간다. 시작은 F(irst)부터다. 자신의 차례에 가져갈 돌이 없거나, 규칙을 만족하면서 돌을 가져가지 못하는 사람이 지고(lose) 상대방은 이기게(win) 된다. 단, 두 사람은 각자의 최선을 다해야 한다. 또한, 빈칸만 채우지 말고 빈칸의 답이 나오게 된 이유를 간단히라도 서술해야 한다. 이를 어길 시 불이익이 있음.

a) 규칙 1. 두 사람이 가져갈 수 있는 돌의 개수는 {1, 3, 4}이다. 이 경우 N=1부터 N=12일 때까지의 승자(winner)를 {F, S}에서 선택하시오. 이를 위한 Dynamic programming 식을 분명히 제사하시오.

N	0	1	2	3	4	5	6	7	8	9	10	11	12
winner	S	F	S	F	F

b) 규칙 2. 2개의 통에 각각 돌이 N, M개 들어있다. 두 사람은 한 통을 선택하여 그 안에서 {1, 3, 4}를 가져갈 수 있다. 이를 위한 Dynamic programming 식을 분명히 제사하rh, (N, M) = (1, 1)부터 (N, M)=(4, 5)일 때까지의 승자(winner)를 {F, S}에서 계산하여 아래 표를 채우시오.

N / M	0	1	2	3	4	5
0	S	F	S	F	F
1	F	S
2	S
3	F
4	F

[4]  크기가 N인 정수 List(array) L이 주어져 있다. 이 리스트(배열)에서 2번째로 작은 원소(second min.)를 찾으려고 한다. 이 함수를 recursion을 이용한 divide and conquer 방식을 사용하는 second_min( ) 함수를 작성하시오. (C++를 사용하려면 array를 사용하시오.)즉 여러분은 index를 사용하는 for loop을 사용해서는 안 된다. 그리고 작성한 코드의 time complexity를 계산하시오. 기본동작은 “비교” 연산이다.

def second_min( L ) :	Complexity

[5] [eqn: n]개의 비트로 구성된 이진 카운터(binary counter)가 있다. 이 장치에 “신호”가 들어갈 때 마다 이 counter의 값은 +1씩 증가한다. 즉 0000에서 신호가 들어올 때 마다 비트는 0001, 0010, 0011, 0100, 0101... 순서로 변화한다. 이때 바뀐 이전 비트와 +1이 된 두 비트에서 바뀐 비트의 갯수를 해당 신호의 “비용(cost)”이라고 정의한다. 즉 [eqn: 0000`` rarrow `000`1] 의 비용은 1이다. 만일 [eqn: 0001111`-> 0010000]로 바뀌어다면 변화된 비트는 모두 5개이므로 이 작업의 비용은 5가 된다.

a) 01101에서 10000까지 변화할 때의 총비용을 계산하시오. (단계별 변화의 합)

b) [eqn: n] 비트 카운터의 시작 [eqn: 000` LDOTS `000]에서 [eqn: 1111 `ldots111]까지 변화할 때의 총비용을 계산하여 그 비용을 점근적 함수(asymptotic function) [eqn: f(n)]으로 표시하시오. 즉 총 [eqn: 2^n -1]개의 step에서 변화된 모든 비트의 수를 계산하면 된다.

c) [eqn: n] 비트 카운터에서 어떤 임의의 비트에서 +1 작업을 할 때 예상(기댓값) 비용을 계산하시오. (즉, 임의의 [eqn: n]비트 값에서 +1을 할 때 바뀌는 비트의 평균 개수(비용))

[6] 다음의 방향 그래프에서 All Pair Shortest Path를 Dynamic Programming을 사용하는 Floyd-Warshall 알고리즘으로 구하려고 한다. 이 방식은 전체 거리 행렬을 계속 update하는 방식으로 진행된다. 아래 그래프를 보고 그 행렬 [eqn: D^{(k)} [i][j]]을 채우시오. 이 알고리즘을  [eqn: k=4]까지 진행하고 이때 변화하는 행렬을 표시하시오.

	1	2	3	4	5
1	0	[eqn: inf]	12	3	[eqn: inf]
2	10	0	+2	[eqn: inf]	[eqn: inf]
3	[eqn: inf]	[eqn: inf]	0	[eqn: inf]	5
4	[eqn: inf]	9	[eqn: inf]	0	[eqn: inf]
5	5	4	[eqn: inf]	[eqn: inf]	0

Graph                                [eqn: D ^{(0)} [i][j]]

a)

[eqn: D^{(k)} [i][j]]의 의미를 기술하시오.

	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

[eqn: D ^{(1)} [i][j]]                                    [eqn: D ^{(2)} [i][j]]

	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

[eqn: D ^{(3)} [i][j]]                                    [eqn: D ^{(4)} [i][j]]